package com.test.daily.leetcode.y2021.m12.day1204;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * LargestSumAfterKNegations
 *
 * @author Tom on 2021/12/3
 */
public class Code01_LargestSumAfterKNegations {
    public static void main(String[] args) {
        Code01_LargestSumAfterKNegations cl= new Code01_LargestSumAfterKNegations();
        int[] nums = new int[]{2,-3,-1,5,-4}; int k = 2;
        System.out.println(cl.largestSumAfterKNegations(nums, k));
    }
    public int largestSumAfterKNegations(int[] nums, int k) {
        int N = nums.length;
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(N,new MyComparator());
        for(int i = 0; i < nums.length; i++){
            pq.add(nums[i]);
        }
        for (int i = 0; i < k; i++) {
            int ele = - pq.poll();
            pq.add(ele);
        }
        int ans = 0;
        while(pq.size() > 0){
            ans += pq.poll();
        }
        return ans;
    }
    class MyComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    }
}
